package graph.medium;

import java.util.*;

/**
 * 网络延迟
 * 有 n 个网络节点，标记为1到 n。
 *
 * 给你一个列表times，表示信号经过 有向 边的传递时间。times[i] = (ui, vi, wi)，
 * 其中ui是源节点，vi是目标节点， wi是一个信号从源节点传递到目标节点的时间。
 *
 * 现在，从某个节点K发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回-1
 *
 * 示例 1：
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/network-delay-time
 */
public class NetworkDelayTime {

//    public int networkDelayTime(int[][] times, int n, int k) {
//        Map<Integer, List<Cell>> map = new HashMap<>();
//        for (int[] time : times) {
//            map.computeIfAbsent(time[0], key -> new ArrayList<>()).add(new Cell(time[1], time[2]));
//        }
//        Map<Integer, Integer> costs = new HashMap<>();
//        PriorityQueue<Cell> minHeap = new PriorityQueue<>((c1, c2) -> c1.time - c2.time);
//        minHeap.offer(new Cell(k, 0));
//        while (!minHeap.isEmpty()) {
//            Cell cur = minHeap.poll();
//            if (costs.containsKey(cur.node)) {
//                continue;
//            }
//            costs.put(cur.node, cur.time);
//            for (Cell cell : map.get(cur.node)) {
//                if (!costs.containsKey(cell.node)) {
//                    minHeap.offer(new Cell(cell.node, cur.time + cell.time));
//                }
//            }
//        }

//    }

    class Cell {

        int node, time;
        Cell(int node, int time) {
            this.node = node;
            this.time = time;
        }

    }
}
